package com.kabuda.zhugehot200_review;

/**
 * @author kabuda
 * @date 2025-03-29 13:01
 * @description
 */
public class 乘积最大子数组 {
    public static void main(String[] args) {
        System.out.println(maxProduct(new int[]{2, 3, -2, -3, 4}));
        System.out.println(maxProduct1(new int[]{2, 3, -2, -3, 4}));
    }


    /**
     * @param nums
     * @author kabuda
     * @date 2025/3/29 13:22
     * @description 暴力破解
     */
    public static int maxProduct(int[] nums) {
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int temp = 1;
            for (int j = i; j < nums.length; j++) {
                max = Math.max(temp *= nums[j], max);
            }
        }
        return max;
    }

    /**
     * @param nums
     * @author kabuda
     * @date 2025/3/29 13:22
     * @description 动态规划
     */
    public static int maxProduct1(int[] nums) {
        int max = Integer.MIN_VALUE;
        int tempMax = 1, tempMin = 1;
        for (int i = 0; i < nums.length; i++) {
            //如果遇到负数，最大最小值交换
            if (nums[i] < 0) {
                int temp = tempMax;
                tempMax = tempMin;
                tempMin = temp;
            }
            //如果遇到正数遇到负数,临时最大值会从当前值开始计算
            tempMax = Math.max(tempMax * nums[i], nums[i]);
            tempMin = Math.min(tempMin * nums[i], nums[i]);

            max = Math.max(tempMax, max);
        }
        return max;
    }
}
